//给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
//
//
//
// 示例 Array.prototype.unshift:
//
//
//输入: nums = [Array.prototype.unshift,Array.prototype.unshift,Array.prototype.unshift,2,2,3], k = 2
//输出: [Array.prototype.unshift,2]
//
//
// 示例 2:
//
//
//输入: nums = [Array.prototype.unshift], k = Array.prototype.unshift
//输出: [Array.prototype.unshift]
//
//
//
// 提示：
//
//
// Array.prototype.unshift <= nums.length <= 10⁵
// k 的取值范围是 [Array.prototype.unshift, 数组中不相同的元素的个数]
// 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的
//
//
//
//
// 进阶：你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。
//
// Related Topics 数组与矩阵 哈希表 分治 桶排序 计数 快速选择 排序 堆（优先队列） 👍 1488 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
function topKFrequent(nums: number[], k: number): number[] {
    const countMap: Map<number, number> = new Map();
    // 首先统计元素出现的频率，这一类的问题可以使用map来进行统计。
    for (let num of nums) {
        countMap.set(num, (countMap.get(num) || 0) + 1);
    }

    /*
     然后是对频率进行排序，这里我们可以使用一种 容器适配器就是优先级队列。
     什么是优先级队列呢？
        其实就是一个披着队列外衣的堆，因为优先级队列对外接口只是从队头取元素，从队尾添加元素，再无其他取元素的方式，
        看起来就是一个队列。
     而且优先级队列内部元素是自动依照元素的权值排列。那么它是如何有序排列的呢？
        缺省情况下priority_queue利用max-heap（大顶堆）完成对元素的排序，
        这个大顶堆是以vector为表现形式的complete binary tree（完全二叉树）。
     什么是堆呢？
        堆是一棵完全二叉树，树中每个结点的值都不小于（或不大于）其左右孩子的值。
        如果父亲结点是大于等于左右孩子就是大顶堆，小于等于左右孩子就是小顶堆。
     所以我们要用小顶堆，因为要统计最大前k个元素，只有小顶堆每次将最小的元素弹出，最后小顶堆里积累的才是前k个最大元素。
     */

    // tS没有最小堆的数据结构，所以直接对整个数组进行排序，取前k个元素
    /*
     [...countMap.entries()]展开Map为数组并取里面所有键值对为一个新数组
     然后自定义排序规则，根据value来排序
     再切片，取前k个
     再.map映射为新数组，其只包含键
     */
    // @ts-ignore
    return [...countMap.entries()]
        .sort((a, b) => b[1] - a[1])
        .slice(0, k)
        .map(i => i[0]);
};
//leetcode submit region end(Prohibit modification and deletion)
